package datastructure.unionfind;

/**
 * 基于路径压缩的优化 降低集合元素树的高度
 */
public class UnionFind5 implements UF {

    //实际表示parent[i]指向那个节点
    private int[] parent;
    //,以i为跟的元素深度记为rank[i]
    private int[] rank;

    public UnionFind5(int size) {
        parent = new int[size];
        this.rank = new int[size];
        //初始的时候，parent[i]=i  指向自己
        for (int i = 0; i < size; i++) {
            parent[i] = i;
            this.rank[i] = 1;
        }
    }

    @Override
    public int getSize() {

        return parent.length;
    }

    // 查看元素p对饮的集合编号  O(h) h为树的高度
    // parent[i]表示第i个元素指向那个节点
    // 向上查找，直到查到跟节点
    private int find(int p) {
        if (p < 0 || p >= parent.length)
            throw new IllegalArgumentException("p is out of bound.");
        while (p != parent[p]) {
            p = parent[p];
            //进行路径压缩
            parent[p] = parent[parent[p]];
        }

        return p;
    }

    @Override
    public boolean isConnected(int p, int q) {
        // 复杂度分析 查找 logn
        int findP = find(p);
        int findQ = find(q);
        return findP == findQ;
    }


    @Override
    public void unionElements(int p, int q) {
        int parentP = find(p);
        int parentQ = find(q);
        if (parentP == parentQ) {
            return;
        } else {

            //根据两个元素所在数的rank不同进行选择合并方向。
            //将rank低的合并到rank高的集合上
            //p>q q 指向p
            if (rank[parentP] > rank[parentQ]) {
                parent[parentQ] = parentP;
            } else if (rank[parentP] < rank[parentQ]) {// p <q  p—>q
                parent[parentP] = parentQ;
            } else {//p==q
                parent[parentP] = parentQ;
                //此时将p-》q的父节点，这样q就会增加一层深度 rank[q]+1
                rank[parentQ] += 1;
            }
        }
    }

}
